//题目:
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int arr_x[]={-1,1,0,0},arr_y[]={0,0,-1,1};
        int ret=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j]=='1')
                {
                    ret++;
                    queue<pair<int,int>> q;//pair内存放的是岛的坐标
                    q.push(make_pair(i,j));
                    grid[i][j]='0';
                    while(!q.empty())
                    {
                        pair<int,int> pir=q.front();
                        q.pop();
                        //将上下左右相邻岛屿入队列
                        for(int k=0;k<4;k++)
                        {
                            int x=pir.first+arr_x[k],y=pir.second+arr_y[k];
                            if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size() && grid[x][y]=='1')
                            {
                                q.push(make_pair(x,y));
                                grid[x][y]='0';
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};
